package com.study.leetcode;

//https://leetcode.cn/problems/search-a-2d-matrix/
public class Solution_74 {
    public static boolean searchMatrix1(int[][] matrix, int target) {
        int row = 0;
        int col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            //跳过比target小的行
            //因为是拿每一行最后一个元素进行的比较所以可以直接锁定到对应的行
            if (matrix[row][col] < target) {
                row++;
            } else if (matrix[row][col] > target) {
                //锁定行后就可以查找列了
                col--;
            } else {
                return true;
            }
        }
        return false;
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int rowLow = 0;
        int rowHigh = matrix[0].length - 1;
        int rowIndex = 0;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][rowLow] <= target && target <= matrix[i][rowHigh]) {
                rowIndex = i;
                break;
            }
        }
        while (rowLow <= rowHigh) {
            int middle = (rowLow + rowHigh) / 2;
            if (matrix[rowIndex][middle] == target) {
                return true;
            } else if (target > matrix[rowIndex][middle]) {
                rowLow = middle + 1;
            } else {
                rowHigh = middle - 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 3, 5, 7},
                {10, 11, 16, 20},
                {23, 30, 34, 60}
        };
        int target = 15;
        boolean b = searchMatrix1(matrix, target);
        System.out.println("b = " + b);
    }
}
